#include <iostream>
#include <stack>
#include <vector>

void printVector(std::vector<int>& vec) {
    for (int i = 0; i < vec.size(); i++) {
        std::cout << vec[i] << " ";
    }

    std::cout << "\n";
}

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {};
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {};
    TreeNode(int x, TreeNode* l, TreeNode* r) : val(x), left(l), right(r) {};
};

std::vector<int> inorderTraversal(TreeNode* root) {
    std::vector<int> result;
    std::stack<TreeNode*> st;

    if (root != nullptr) st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        if (node != NULL) {
            st.pop();

            if (node->right) st.push(node->right);

            st.push(node);
            st.push(NULL);

            if (node->left) st.push(node->left);
        } else {
            st.pop();
            result.push_back(st.top()->val);
            st.pop();
        }
    }

    return result;
}

int main() {
    TreeNode* root = new TreeNode(10);
    TreeNode* node1 = new TreeNode(6);
    TreeNode* node2 = new TreeNode(16);
    TreeNode* node3 = new TreeNode(3);
    TreeNode* node4 = new TreeNode(9);
    TreeNode* node5 = new TreeNode(14);
    TreeNode* node6 = new TreeNode(19);
    root->left = node1;
    root->right = node2;
    node1->left = node3;
    node1->right = node4;
    node2->left = node5;
    node2->right = node6;

    std::vector<int> res = inorderTraversal(root);
    std::cout << "inorder: \n";
    printVector(res);
}